The minmax multidimensional knapsack problem with application to a chance‐constrained problem

In this paper we present a new combinatorial problem, called minmax multidimensional knapsack problem (MKP), motivated by a military logistics problem. The logistics problem is a two‐period, two‐level, chance‐constrained problem with recourse. We show that the MKP is NP‐hard and develop a practically efficient combinatorial algorithm for solving it. We also show that under some reasonable assumptions regarding the operational setting of the logistics problem, the chance‐constrained optimization problem is decomposable into a series of MKPs that are solved separately. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

导弹贮存寿命预估的组合模型

在分析比较了几种寿命预估方法优缺点的基础上,针对单一预估方法在解决实际问题中所暴露的局限性,优选了GM-BPNN组合预估模型。该组合模型既利用了灰色预估理论具有所需要的样本数据少、原理简单、运算方便、短期预估精度高、可检验等优点,也发挥了神经网络并行计算、容错能力强、自适应能力强等优点。最后利用该组合模型对弹上某设备寿命进行了预估,取得了较好的预测效果。     

联合作战系统效能评估

采用面向过程的系统分析方法建立了一个对联合作战系统效能比较精确的量化评估模型.模型以某个参考系统为标准,先作层次分析,然后通过模糊对比,把各层次中难以具体量化因素进行了量化,再通过判断矩阵得出各自权重,最后线性加权便可以得到总的系统相对于标准系统的优劣程度,是一种面向过程的系统分析.该方法适用面广,对复杂系统效能评估工作有一定指导意义,具有广阔的应用前景.     

炮兵指挥信息系统综合训练质量评估

针对炮兵指挥信息系统综合训练质量评估的复杂性,按照"三位一体"的原则,全面考虑评估目的、被评对象特点、评估方法三者之间的协调一致性,采用了多级模糊综合评价方法与因子分析法相结合的组合评价方法,既实现了对训练质量的量化评估排序,又查找分析了影响综合训练质量的因素,经实例验证可行有效。     

Exponential size neighborhoods for makespan minimization scheduling

We investigate the quality of local search heuristics for the scheduling problem of minimizing the makespan on identical parallel machines. We study exponential size neighborhoods (whose size grows exponentially with the input length) that can be searched in polynomial time, and we derive worst‐case approximation guarantees for the local optima of such neighborhoods. The so‐called split neighborhood splits a feasible schedule into two layers, and then recombines the two layers by finding a perfect matching. We show that the makespan of every local optimum for split is at most a factor of 2 away from the globally optimal makespan. We then combine the split neighborhood with two neighborhoods from the literature. The combination of split with the jump neighborhood only marginally improves the approximation guarantee, whereas the combination with the lexicographic‐jump neighborhood decreases the approximation guarantee from 2 to 3/2. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

鱼雷衡重特性对初始弹道的影响分析

建立了鱼雷水下空间弹道数学模型,并针对鱼雷不同的衡重特性,采用四阶龙格库塔法和全选主元高斯消去法进行了仿真计算,分别研究了不同自由角、管制舵角和初始速度时初始弹道的变化规律.仿真结果表明,在质量相对较小、质浮心距离较大时,鱼雷初始弹道更易出现拱水现象,因而不适于在浅深度发射;在质量相对较大、质浮心距离很小时,鱼雷初始弹道出现较大袋深,发射时要求大深度海区.这些现象只能在一定程度上通过调整管制舵角、自由角和发射初始速度来克服.     

航空时敏制导炸弹增程弹道组合优化设计

为增强航空时敏制导炸弹在中制导段的滑翔能力,将极小值原理与自适应进化粒子群算法相结合,提出了一种适用于航空时敏制导炸弹增程弹道的组合优化设计方法。基于纵向平面内质心运动模型,推导了性能指标泛函及各不等式约束函数。引入Lagrange乘子矢量并建立相应的Hamilton函数实现无约束泛函极值问题的转换,推导出兼顾各优化目标函数的满意优化模型。利用自适应进化粒子群算法对该段增程弹道进行了攻角与弹翼张合档位双设计变量的组合优化。数值仿真算例表明,在满足状态方程约束的条件下,双变量的增程效果比常规单变量控制时显著提高,其优化结果可为制导炸弹弹道规划设计的研究提供一定的理论参考。     

Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost

In the last decade, there has been much progress in understanding scheduling problems in which selfish jobs aim to minimize their individual completion time. Most of this work has focused on makespan minimization as social objective. In contrast, we consider as social cost the total weighted completion time, that is, the sum of the agent costs, a standard definition of welfare in economics. In our setting, jobs are processed on restricted uniform parallel machines, where each machine has a speed and is only capable of processing a subset of jobs; a job's cost is its weighted completion time; and each machine sequences its jobs in weighted shortest processing time (WSPT) order. Whereas for the makespan social cost the price of anarchy is not bounded by a constant in most environments, we show that for our minsum social objective the price of anarchy is bounded above by a small constant, independent of the instance. Specifically, we show that the price of anarchy is exactly 2 for the class of unit jobs, unit speed instances where the finite processing time values define the edge set of a forest with the machines as nodes. For the general case of mixed job strategies and restricted uniform machines, we prove that the price of anarchy equals 4. From a classical machine scheduling perspective, our results establish the same constant performance guarantees for WSPT list scheduling. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Iterative coloring extension of a maximum clique

In this paper we present an improved branch and bound algorithm for the vertex coloring problem. The idea is to try to extend the coloring of a maximum clique to its adjacent vertices. If this succeeds, its successive neighbors are considered; in case of failure (i.e., in the case the initial colors are not sufficient), working on the subgraph induced by the maximum clique and its neighborhood, the lower bound is improved by seeking for an optimal coloring of this subgraph by branch and bound. The process is repeated iteratively until the whole graph is examined. The iterative scheme exploits a further lower bound obtained by integrating a simple algorithm into the maximum clique search, and a new method to compute upper bounds on subgraphs. Furthermore, a new branching rule and a method for the selection of the initial maximum clique are presented. Extensive computational results and comparisons with existing exact coloring algorithms on random graphs and benchmarks are given. © 2001 John Wiley & Sons, Inc. Naval Research Logistic 48: 518–550, 2001     

灰色模糊物元分析的要地防空威胁评估

结合要地防空作战的特点,分析了影响目标威胁评估的因素.针对指标信息的不确定性,将模糊物元分析与灰色系统理论相结合,并运用AHP法和信息熵法进行组合赋权,建立了基于组合赋权的灰色模糊物元分析的要地防空威胁评估模型.在对来袭目标进行威胁评估时,将目标的各个特征作为物元的事物,以其各项评价指标及模糊灰量值构造复合模糊灰元.通过计算与标准模糊灰元之间的关联度,实现对空袭目标的威胁评估与排序.实例分析表明该方法可靠有效.